Search results for "Mobile automaton"
showing 10 items of 18 documents
Research of Complex Forms in Cellular Automata by Evolutionary Algorithms
2004
This paper presents an evolutionary approach for the search for new complex cellular automata. Two evolutionary algorithms are used: the first one discovers rules supporting gliders and periodic patterns, and the second one discovers glider guns in cellular automata. An automaton allowing us to simulate AND and NOT gates is discovered. The results are a step toward the general simulation of Boolean circuits by this automaton and show that the evolutionary approach is a promising technic for searching for cellular automata that support universal computation.
Deterministic generalized automata
1995
A generalized automaton (GA) is a finite automaton where the single transitions are defined on words rather than on single letters. Generalized automata were considered by K. Hashiguchi who proved that the problem of calculating the size of a minimal GA is decidable.
Language Recognition Power and Succinctness of Affine Automata
2016
In this work we study a non-linear generalization based on affine transformations of probabilistic and quantum automata proposed recently by Diaz-Caro and Yakaryilmaz [6] referred as affine automata. First, we present efficient simulations of probabilistic and quantum automata by means of affine automata which allows us to characterize the class of exclusive stochastic languages. Then, we initiate a study on the succintness of affine automata. In particular, we show that an infinite family of unary regular languages can be recognized by 2-state affine automata, whereas the number of states of any quantum and probabilistic automata cannot be bounded. Finally, we present the characterization …
One Alternation Can Be More Powerful Than Randomization in Small and Fast Two-Way Finite Automata
2013
We show a family of languages that can be recognized by a family of linear-size alternating one-way finite automata with one alternation but cannot be recognized by any family of polynomial-size bounded-error two-way probabilistic finite automata with the expected runtime bounded by a polynomial. In terms of finite automata complexity theory this means that neither 1Σ2 nor 1Π2 is contained in 2P2.
Quantum Finite Multitape Automata
1999
Quantum finite automata were introduced by C. Moore, J. P. Crutchfield [4], and by A. Kondacs and J. Watrous [3]. This notion is not a generalization of the deterministic finite automata. Moreover, in [3] it was proved that not all regular languages can be recognized by quantum finite automata. A. Ambainis and R. Freivalds [1] proved that for some languages quantum finite automata may be exponentially more concise rather than both deterministic and probabilistic finite automata. In this paper we introduce the notion of quantum finite multitape automata and prove that there is a language recognized by a quantum finite automaton but not by deterministic or probabilistic finite automata. This …
Probabilistic Reversible Automata and Quantum Automata
2002
To study relationship between quantum finite automata and probabilistic finite automata, we introduce a notion of probabilistic reversible automata (PRA, or doubly stochastic automata). We find that there is a strong relationship between different possible models of PRA and corresponding models of quantum finite automata. We also propose a classification of reversible finite 1-way automata.
Improved constructions of quantum automata
2008
We present a simple construction of quantum automata which achieve an exponential advantage over classical finite automata. Our automata use \frac{4}{\epsilon} \log 2p + O(1) states to recognize a language that requires p states classically. The construction is both substantially simpler and achieves a better constant in the front of \log p than the previously known construction of Ambainis and Freivalds (quant-ph/9802062). Similarly to Ambainis and Freivalds, our construction is by a probabilistic argument. We consider the possibility to derandomize it and present some results in this direction.
Group Input Machine
2009
We introduce a new type of internal memory for finite automata and real-time automata. Instead of using tapes with a prescribed Euclidean structure (one-dimensional or two-dimensional tapes) we allow arbitrary group structure of the internal memory of the automata.
Extremal minimality conditions on automata
2012
AbstractIn this paper we investigate the minimality problem of DFAs by varying the set of final states. In other words, we are interested on how the choice of the final states can affect the minimality of the automata. The state-pair graph is a useful tool to investigate such a problem. The choice of a set of final states for the automaton A defines a coloring of the closed components of the state-pair graph and the minimality of A corresponds to a property of these colored components. A particular attention is devoted to the analysis of some extremal cases such as, for example, the automata that are minimal for any choice of the subset of final states F from the state set Q of the automato…
Classical automata on promise problems
2015
Promise problems were mainly studied in quantum automata theory. Here we focus on state complexity of classical automata for promise problems. First, it was known that there is a family of unary promise problems solvable by quantum automata by using a single qubit, but the number of states required by corresponding one-way deterministic automata cannot be bounded by a constant. For this family, we show that even two-way nondeterminism does not help to save a single state. By comparing this with the corresponding state complexity of alternating machines, we then get a tight exponential gap between two-way nondeterministic and one-way alternating automata solving unary promise problems. Secon…